package com.mdnote.practice.binary_search;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/18
 * @description 有效的完全平方数
 */
public class LeetCode367 {

    public static void main(String[] args)    {
        LeetCode367 leetCode267 = new LeetCode367();
        boolean perfectSquare = leetCode267.isPerfectSquare(14);
        System.out.println(perfectSquare);
    }
    public boolean isPerfectSquare(int num) {

        // binary search
//        int res = binarySearch(num);

        // for loop
        int res = forLoop(num);
        return  res * res == num;
    }

    private int forLoop(int num) {

        double Xn = num, C = num;
        while (true) {
            double Xn1 = 0.5 * (Xn + C / Xn);
            if (Math.abs(Xn1 - Xn) < 1e-7) {
                break;
            }
            Xn = Xn1;
        }
        return (int) Xn;
    }

    private int binarySearch(int num) {

        int left = 0;
        int right = num;

        int res = 0;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (mid * mid == num) {
                return mid;
            } else if (mid * mid > num) {
                right = mid - 1;
            } else {
                res = mid;
                left = mid + 1;
            }
        }
        return res;
    }


}
